package 纯数组;

public class No1011在D天内送达包裹的能力 {

    /**
     * 传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。
     * 传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
     * 返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。
     *
     * 示例 1：
     * 输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5
     * 输出：15
     * 解释：
     * 船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
     * 第 1 天：1, 2, 3, 4, 5
     * 第 2 天：6, 7
     * 第 3 天：8
     * 第 4 天：9
     * 第 5 天：10
     * 请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。
     * 示例 2：
     * 输入：weights = [3,2,2,4,1,4], D = 3
     * 输出：6
     * 解释：
     * 船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示：
     * 第 1 天：3, 2
     * 第 2 天：2, 4
     * 第 3 天：1, 4
     * 示例 3：
     * 输入：weights = [1,2,3,1,1], D = 4
     * 输出：3
     * 解释：
     * 第 1 天：1
     * 第 2 天：2
     * 第 3 天：3
     * 第 4 天：1, 1
     *  
     * 提示：
     * 1 <= D <= weights.length <= 50000
     * 1 <= weights[i] <= 500
     */

    /**
     * 解题方法: 依次找适合的重量
     */
    public int shipWithinDays(int[] weights, int D) {

        int maxWeight=Integer.MIN_VALUE;

        int sum=0;
        for (int weight : weights) {
            sum+=weight;
            maxWeight=Math.max(maxWeight,weight);
        }
        if(D==1){
            return sum;
        }

        //一次最少maxWeight那么重  最多sum那么重
        int left=maxWeight;
        int right=sum;
        int mid;

        while (left<=right){
            mid=(right-left)/2+left;
            boolean isOk=isOk(weights,D,mid);
            if(isOk){
                //选当前这么重,可以运完,继续压缩空间
                right=mid-1;
            }else{
                //不可运完,放大空间
                left=mid+1;
            }

        }

        return left;
    }

    private boolean isOk(int[] weights,int D,int itemWeight){
        int tempWeight=itemWeight;
        int countD=0;
        for (int i = 0; i < weights.length; i++) {
            if(itemWeight-weights[i]<0){
                //今天带不下这么多,出发了
                countD++;
                itemWeight=tempWeight;
                i--;//吐出本次货物
            }else{
                //今天可以运完
                itemWeight-=weights[i];
            }
            if((countD+1)>D){//加1,因为最后一次运输时的次数还没有加上
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        No1011在D天内送达包裹的能力 n=new No1011在D天内送达包裹的能力();
        int[] arr={1,2,3,4,5,6,7,8,9,10};
        int result = n.shipWithinDays(arr, 5);
        System.out.println(result);
    }

}
